`
https://leetcode.cn/problems/cheapest-flights-within-k-stops/
`

/**
 * @param {number} n
 * @param {number[][]} flights
 * @param {number} src
 * @param {number} dst
 * @param {number} k
 * @return {number}
 */
var findCheapestPrice = function (n, flights, src, dst, k) {
  const graph = Array.from({ length: n }, () => [])
  for (const [from, to, price] of flights) {
    graph[from].push([to, price])
  }

  // Dijkstra with limit
  const distTo = new Array(n).fill(-1)
  const edges = new Array(n).fill(Infinity)
  const pq = new Heap((a, b) => a.distFromStart - b.distFromStart)
  pq.push(new State(src, 0, 0))
  distTo[src] = 0
  edges[src] = 0

  while (!pq.isEmpty()) {
    const state = pq.pop()
    const curNode = state.node
    const curDistFromStart = state.distFromStart
    const curEdgesFromStart = state.edgesFromStart

    // 不是第一次遍历且当前走的比之前走的还多，跳过
    if (distTo[curNode] !== -1 && curEdgesFromStart > edges[curNode]) {
      continue
    }

    // 第一次遍历到，更新答案
    if (distTo[curNode] === -1) {
      distTo[curNode] = curDistFromStart
      // 遇到终点，直接返回答案
      if (curNode === dst) {
        return curDistFromStart
      }
    }
    edges[curNode] = Math.min(edges[curNode], curEdgesFromStart)

    for (const [nextNode, price] of graph[curNode]) {
      const nextDistFromStart = curDistFromStart + price
      const nextEdgesFromStart = curEdgesFromStart + 1

      // 如果下个节点已经遍历过且走过去的站点数比之前的还多，跳过
      if (distTo[nextNode] !== -1 && nextEdgesFromStart > edges[nextNode]) {
        continue
      }

      // 如果走过去已经超过了中转上线，跳过
      // 题目要求最多经过 k 站中转，也就是最多经过 k + 1 条边
      if (nextEdgesFromStart > k + 1) {
        continue
      }

      pq.push(new State(nextNode, nextDistFromStart, nextEdgesFromStart))
    }
  }

  // 没找到
  return -1
};

class State {
  constructor(node, distFromStart, edgesFromStart) {
    this.node = node
    this.distFromStart = distFromStart
    this.edgesFromStart = edgesFromStart
  }
}